package pro.softzhang.algo.lc0;

public class LC97_InterleavingString {
    public static void main(String[] args) {

    }

    static class Solution {
        public boolean isInterleave(String s1, String s2, String s3) {
            if(s1.length() + s2.length() != s3.length()) {
                return false;
            }

            if(s1.length() < s2.length()) {
                return isInterleave(s2, s1, s3);
            }

            boolean[] dp = new boolean[s2.length() + 1];
            dp[0] = true;
            for (int j = 0; j < s2.length(); j++) {
                dp[j + 1] = s2.charAt(j) == s3.charAt(j) && dp[j];
            }

            for (int i = 0; i < s1.length(); i++) {
                dp[0] = dp[0] && s1.charAt(i) == s3.charAt(i);
                for (int j = 0; j < s2.length(); j++) {
                    char ch1 = s1.charAt(i);
                    char ch2 = s2.charAt(j);
                    char ch3 = s3.charAt(i + j + 1);
                    dp[j + 1] = (ch1 == ch3 && dp[j + 1]) || (ch2 == ch3 && dp[j]);
                }
            }
            return dp[s2.length()];
        }
    }
}
